1. Field of the Invention
This invention generally relates to digital communications and, more particularly, to a system and method for the efficient coding of parity data in communications encoded with forward error correction (FEC).
2. Description of the Related Art
A parity bit is a bit that is added to ensure that the number of bits with the value one in a set of bits is even or odd. Parity bits are used as the simplest form of error detecting code. When using even parity, the parity bit is set to 1 if the number of ones in a given set of bits (not including the parity bit) is odd, making the entire set of bits (including the parity bit) even. When using odd parity, the parity bit is set to 1 if the number of ones in a given set of bits (not including the parity bit) is even, making the entire set of bits (including the parity bit) odd. In other words, an even parity bit will be set to “1” if the number of 1's+1 is even, and an odd parity bit will be set to “1” if the number of 1's+1 is odd. It can be calculated via an exclusive-or (XOR) sum of the bits. This property of being dependent upon all the bits, and changing value if any one bit changes, allows for its use in error detection schemes. For example, if an odd number of bits (including the parity bit) is transmitted incorrectly, the parity bit may be incorrect, indicating that an error occurred in transmission. This type of parity bit is only suitable for detecting errors; it cannot correct any errors, as there is no way to determine which particular bit is corrupted. The data must be discarded entirely, and re-transmitted from scratch. However, parity has the advantage that it uses only a single bit and requires only a number of XOR gates to generate.
Given enough parity data, incorrectly received information can be corrected. In information theory, a low-density parity-check (LDPC) code is a linear error correcting code method of transmitting a message over a noisy transmission channel. LDPC codes are finding increasing use in applications where reliable and highly efficient information transfer is desired over bandwidth or return channel constrained links in the presence of data-corrupting noise. LDPC codes are defined by a sparse parity-check matrix.
FIG. 1 is diagram of a parity matrix of an XOR matrix tree for generating codewords (prior art).
C is the codeword array: 1×2048;
G is the generating matrix: 2048×1723; and,
U is the input array: 1723×1.
Each codeword (C) is a combination of the original user word (U) and parity bits. In this case, there are 325 parity bits (2048−1723) in each codeword. Each bit in the codeword is generated by XORing a combination of bits in the user word. The combination of user word bits used to create the parity bit is determined by the value of P.C1×2048=G2048×1723*u1723×1 
      [          c      2048        ]    =            [                                                  I                              1723                ×                1723                                                                                        P                              325                ×                1723                                                        ]        *          [              u        1723            ]      
      [                  c        0            ⁢              c        1            ⁢                          ⁢      …      ⁢                          ⁢              c        2047              ]    =            [                                                  [                                                                                          1                      ⁢                                                                                          ⁢                      …                                                                                                  0                      ⁢                                                                                          ⁢                      …                                                                                                  0                      ⁢                                                                                          ⁢                      …                                                                                                  0                      ⁢                                                                                          ⁢                      …                                                                            0                                                                                                              0                      ⁢                                                                                          ⁢                      …                                                                                                  1                      ⁢                                                                                          ⁢                      …                                                                                                  0                      ⁢                                                                                          ⁢                      …                                                                                                  0                      ⁢                                                                                          ⁢                      …                                                                                                  0                      ⁢                                                                                          ⁢                      …                                                                                                            ⋮                                                        ⋮                                                        ⋮                                                        ⋮                                                        ⋮                                                                                                              0                      ⁢                                                                                          ⁢                      …                                                                                                  0                      ⁢                                                                                          ⁢                      …                                                                                                  0                      ⁢                                                                                          ⁢                      …                                                                                                  1                      ⁢                                                                                          ⁢                      …                                                                            0                                                                                                              0                      ⁢                                                                                          ⁢                      …                                                                                                  0                      ⁢                                                                                          ⁢                      …                                                                                                  0                      ⁢                                                                                          ⁢                      …                                                                                                  0                      ⁢                                                                                          ⁢                      …                                                                            1                                                              ]                                                                          [                                                                                          P                                              0                        ,                        0                                                                                                  …                                                        …                                                        …                                                                              P                                              0                        ,                        1722                                                                                                                                  ⋮                                                        …                                                        …                                                        …                                                        ⋮                                                                                                              P                                              324                        ,                        0                                                                                                  …                                                        …                                                        …                                                                              P                                              324                        ,                        1722                                                                                                        ]                                          ]        *          [                                                  u              0                                                                          u              1                                                            ⋮                                                ⋮                                                              u              1722                                          ]      
While parity bits are useful in determining errors and correcting errors in transmitted messages, forming the parity bits requires extra hardware or processing time, additional memory, and it adds delay to the transmission of messages.
It would be advantageous if the calculation of parity bits could be simplified.
It would be advantageous if a lookup table-based efficient 10-GBaseT LDPC encoder design existed.